---
title: 树
description: 最多只有一个入度，多个出度
---
## 基础概念
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/img/202410101147592.png"/>

树是n个节点的有限集合（n>=0）,当 n = 0 时称为空树，在任一棵非空树中，<RedSpan>有且仅有一个根节点。</RedSpan>其余节点可分为 <RedSpan>m(m>=0)个互不相交的有限子集 T1,T2,...,Tm，其中，每个 Ti 都是一棵树</RedSpan>，并且称为根节点的子树。

树的基本概念如下：
* <RedSpan>双亲、孩子和兄弟。</RedSpan>结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点双亲；具有相同双亲的结点互为兄弟。
* <RedSpan>结点的度。</RedSpan>一个结点的子树的个数称为该结点的度。例如 A 的度是 3，B 的度是 2，C 的度是 0，D的度是 1。（相当于只算了出度，出度和入度是图中的概念）
* <RedSpan>叶子结点</RedSpan>：叶子结点也称为终端结点，指度为 0 的节点，例如 E、F、C、G 都是叶子节点
* <RedSpan>内部节点</RedSpan>：度不为零的节点，也称为分支结点或非终端结点。除根节点外，分支结点也称为内部节点。例如 B、D 都是内部结点。
* <RedSpan>结点的层次</RedSpan>。根为第一层，根的孩子为第二层，依次类推，若某结点在第 i 层，则其孩子结点在 i+1 层。例如，A 在第 1 层，B、C、D 在第 2 层，E、F、G 在第 3 层。
* <RedSpan>树的高度</RedSpan>。一棵树的最大层数记为树的高度（深度）。例如，图中所示树的高度为 3。
* <RedSpan>有序（无序）树</RedSpan>。若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。


## 二叉树
二叉树是 n 个结点的有限集合，它或者是空树，或者是由一个根结点及 <RedSpan>两颗互不相交的且分别称为左右子树的二叉树组成。</RedSpan>

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241012000951.png"/>

两种特殊的二叉树如下图所示：

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241012001023.png"/>

* 满二叉树：除了叶子结点，其余结点的度都是 2 。
* 完全二叉树：从左到右，元素是不间断的。

二叉树有一些性质如下，要求掌握，在实际考试中可以使用特殊值法验证。
1. 二叉树 <RedSpan>第 i 层（i>=1）上至少有 $2^{i-1}$个结点</RedSpan>
2. 深度为 k 的二叉树至多有 <RedSpan>$2^k-1$个结点（k>=1)</RedSpan>。（等比数列求和）
3. 对任何一颗二叉树，若其 <RedSpan>终端结点数为 $n_0$,度为 2 的结点树为 $n_2$，则 $n_0 = n_2+1$</RedSpan>

:::tip
上面的公式可以画一个简单的二叉树使用特殊值法快速验证，也可以证明如下：
设一棵二叉树上 <RedSpan>叶子结点树为 $n_0$,单分支结点数为 $n_1$，双分支结点数为 $n_2$</RedSpan>，则总结点数为 $n_1+n_2+n_0$，在一颗二叉树中，所有结点的分支数（即度数）应该等于单分支结点数加上双分支结点数的2倍，即总的分支数=$n_1+2n_2$。由于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总的分支数 = 总结点数 - 1。


所以 $n_1+2n_2= n_1+n_2+n_0-1$ , 得到 $n_0=n_2+1$。
:::

4. 具有 <RedSpan>n个结点的完全二叉树的深度为 $\lfloor log_2n \rfloor +1$ (向下取整)</RedSpan>


## 二叉树的存储
### 顺序存储
就是用一组 <RedSpan>连续的存储单元存储二叉树中的节点</RedSpan>，按照 <RedSpan>从上到下、从左到右的顺序依次存储每个节点。</RedSpan>

对于 <RedSpan>深度为k的完全二叉树</RedSpan>，除第 k 层外，其余每层中节点数都是上一层的 2 倍，由此，从一个节点的编号可以推测其双亲、左孩子和右孩子节点的编号。假设有 <RedSpan>编号为 i 的节点，</RedSpan>则有：
* 若 i  = 1，则该节点为根节点，无双亲；若 i >1,则该节点的双亲节点为 [i/2]。
* 若 <RedSpan> `2i<=n` ,则该节点的左孩子编号为 2i,否则无左孩子</RedSpan>
* 若 <RedSpan> `2i+1<=n`,则该节点的右孩子编号为 2i+1,否则无右孩子。</RedSpan>

显然，顺序存储结构对于完全二叉树而言既简单又节省空间，而<RedSpan>对于一般二叉树则不适用</RedSpan>。因为在顺序存储结构中，以节点在存储单元中的位置来表示节点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要 <RedSpan>添上一些实际上并不存在的“虚节点“，这将造成空间的浪费。</RedSpan>


### 链式存储
由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用 <RedSpan>三叉链表或二叉链表</RedSpan>（即一个节点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根节点。


<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241013222405.png"/>


## 二叉树的遍历
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/img/202410141707451.png"/>

一棵非空的二叉树由根节点、左子树、右子树三部分组成，遍历这三部分，也就遍历了整棵二叉树。这三部分遍历的<RedSpan>基本顺序是先左子树后右子树，但根节点顺序可变，以根节点访问的顺序为准有以下三种遍历方式：</RedSpan>
* <RedSpan> 先序：（前序）遍历，根左右</RedSpan>
* <RedSpan> 中序：左根右</RedSpan>
* <RedSpan> 后序：左右根</RedSpan>

示例：前序：12457836 ；中序：42785136；后序：48752631



层次遍历：按层次，从上到下，从左到右。

### 反向构造二叉树

仅仅有前序和后序是无法构造二叉树的，<RedSpan>必须配合中序遍历才能反向构造出二叉树</RedSpan>。

构造时，<RedSpan>前序和后续遍历可以确定根节点，中序遍历用来确定根节点的左子树节点和右子树节点</RedSpan>，而后按此方法进行递归，直至得出结果。
## 线索二叉树

引入线索二叉树是为了保存 <RedSpan>二叉树遍历时某节点的前驱节点和后继节点的信息，</RedSpan>二叉树的链式存储只能获取到某节点的左孩子和右孩子节点，无法获取其遍历时的前驱和后继节点，因此可以在 <RedSpan>链式存储中再增加两个指针域，使其分别指向前驱和后继节点，但这样太浪费存储空间，考虑下述实现方法：</RedSpan>：
* 若 <RedSpan>n个节点的二叉树使用二叉链表存储，则必然有 n+1 个空指针域</RedSpan>，利用这些空指针域来存放节点的前驱和后继节点信息，为此，需要增加两个标记，以区分指针域存放的到底是孩子节点还是遍历节点。
<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/img/202410141829950.png"/>
* 若二叉树的二叉链表采用上述结构，则称为 <RedSpan>线索链表，其中指向前驱、后继节点的指针称为线索，</RedSpan>加上线索的二叉树称为线索二叉树。

* ltag = 1 时 lchild 域指向节点的直接前驱动，否则指向节点的左孩子；rtag = 1 时 rchild 域指向节点的直接后继。

:::tip 为什么n个节点的二叉树使用二叉链表存储，则必然有 n+1 个空指针域？
n 个节点使用二叉链表存储一共有 2n 个指针域，n 个节点所以用了 n 个，因为每一个节点都有一个指针域指向它（除了根节点），所以 2n-(n-1) = n+1。
:::
## 最优二叉树（哈夫曼树）
<RedSpan>最优二叉树又称为哈夫曼树</RedSpan>，是一类<RedSpan>带权路径长度最短的树</RedSpan>，相关概念如下：
* 路径: 树中<RedSpan>一个结点到另一个结点之间的通路</RedSpan>。
* 结点的路径长度：<RedSpan>路径上的分支数目</RedSpan>
* 树的路径长度：<RedSpan>根节点到达每一个叶子节点之间的路径长度之和</RedSpan>
* 权：节点<RedSpan>代表的值</RedSpan>
* 节点的带权路径长度：<RedSpan>该节点到根节点之间的路径长度乘以该节点的权值</RedSpan>。
* 树的带权路径长度（树的代价）：<RedSpan>树的所有叶子节点的带权路径长度之和</RedSpan>

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241014213129.png"/>

哈夫曼树的求法: 给出一组权值，将其中 <RedSpan>两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到改组权值中。</RedSpan>重复进行上述步骤，直至所有权值都被使用完。

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241014214522.png"/>

通过上述步骤求出的树的带权路径长度时最小的

**若需要构造<RedSpan>哈夫曼树</RedSpan>(要保证<RedSpan>左节点值小于右节点的值，才是标准的哈夫曼树</RedSpan>），将标准哈夫曼树的<RedSpan>左分支设为0，右分支设为1，</RedSpan>写出每个叶子节点的编码，会发现，哈夫曼编码的前缀不同，因此不会混淆，同时也是最优编码**
## 查找二叉树
查找（排序）二叉树上的每个节点都存储一个值，且 <RedSpan>每个节点的所有左孩子节点值都小于父节点值，而所有右孩子节点值都大于父节点值，</RedSpan>是一个有规律排列的二叉树，这种数据结构可以方便查找、插入等数据操作。

<RedSpan>二叉排序树的查找效率取决于二叉排序树的深度</RedSpan>，对于节点个数相同的二叉排序树。平衡二叉树的深度最小，而 <RedSpan>单枝树的深度是最大的，故效率最差</RedSpan>。

## 平衡二叉树
平衡二叉树又称为 <RedSpan>AVL 树</RedSpan>,它或者是一棵空树，或者是具有下列性质的二叉树。
* 它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过 1。
* 若将二叉树节点的 <RedSpan>平衡因子（Balance Factor，BF）定义为该节点的左子树高度减去其右子树的高度，</RedSpan>则平衡二叉树上的所有节点的平衡因子只可能是 -1 、0、1 。只要树上有一个节点的平衡因子的绝对值大于 1， 则该二叉树就是不平衡的。

